// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-01 00:06
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CanReorderDoubled {
    /**
     * 二倍数对数组
     * 1 判断传入数据是奇数还是偶数
     * 奇数只能*2
     * 偶数需要双向判断
     * 数组hash
     * (2 4) (8 16)
     * (1 1) (1 1)
     * 2 (4 8) 16
     * 1 (1 1) 1
     */
    public boolean canReorderDoubled(int[] arr) {
        int N = 100010, n = arr.length, max = Integer.MIN_VALUE;
        int[] cnt = new int[2 * N];
        Arrays.fill(cnt, 0);
        for (int j : arr) {
            int sit = j + N;
            cnt[sit]++;
            max = Math.max(max, sit);
        }
        boolean isN = false;
        for (int i = 0; i <= max; i++) {
            isN = i < N;
            while (cnt[i] > 0) {
                if (isN) {
                    if (i % 2 == 1) {
                        return false;
                    }
                    // 当前是负数
                    if (cnt[(i - N) / 2 + N] <= 0) {
                        return false;
                    } else {
                        cnt[(i - N) / 2 + N]--;
                    }
                } else {
                    // 当前是正数
                    if (cnt[2 * i - N] <= 0) {
                        return false;
                    } else {
                        cnt[2 * i - N]--;
                    }
                }
                cnt[i]--;
            }
        }
        return true;
    }

    @Test
    public void shout() {
        int[] test = {-5, -2};
        System.out.println(canReorderDoubled(test));
    }


    /**
     * 使用HashMap
     */
    public boolean canReorderDoubledT(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(2 * num)) {
                if (map.get(2 * num) == 1) {
                    map.remove(2 * num);
                } else {
                    map.put(2 * num, map.get(2 * num) - 1);
                }
            } else if (map.containsKey(num / 2)) {
                if (map.get(num / 2) == 1) {
                    map.remove(num / 2);
                } else {
                    map.put(num / 2, map.get(num / 2) - 1);
                }
            } else {

            }
        }
        return map.isEmpty();
    }
}
